package com.zklh.leetcode.interviewTop150;

import java.util.*;

/**
 * 克隆图算法实现
 * author: tongnan
 * date: 2024/8/7
 */
public class Solution133 {
    static class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
    }

    Map<Integer, Node> visitedMap = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        if (visitedMap.containsKey(node.val)) {
            return visitedMap.get(node.val);
        }

        Node cpNode = new Node(node.val);
        visitedMap.put(cpNode.val, cpNode);
        for (Node neighbor : node.neighbors) {
            cpNode.neighbors.add(cloneGraph(neighbor));
        }
        return cpNode;
    }
}
